#include "c_algorithmic.h"

C_ARRAY void* array_Maxheapify(C_ARRAY void *array,void *ptr,BOOL_ (*compare)(void *lhs,void *rhs))
{
	char tmp[array_Head(array)->data_size];
	void *last=NULL;

	if(heap_Left(array,ptr)!=NULL)if(compare(heap_Left(array,ptr),ptr)==TRUE_)last=heap_Left(array,ptr);
	if(heap_Right(array,ptr)!=NULL)
	{
		if(last==NULL)
		{
			if(compare(heap_Right(array,ptr),ptr)==TRUE_)last=heap_Right(array,ptr);
		}
		else
		{
			if(compare(heap_Right(array,ptr),last)==TRUE_)last=heap_Right(array,ptr);
		};
	};

	if(last!=NULL)
	{
		memcpy(tmp,last,array_Head(array)->data_size);
		memcpy(last,ptr,array_Head(array)->data_size);
		memcpy(ptr,tmp,array_Head(array)->data_size);
		array_Maxheapify(array,last,compare);
	};
	return array;
};

C_ARRAY void* array_Sort(C_ARRAY void *array,BOOL_ (*compare)(void *lhs,void *rhs))
{
	char tmp[array_Head(array)->data_size];
	char *ptr;
	char *last;
	size_t length;

	for(ptr=&((char*)array)[array_Length(array)/2*array_Head(array)->data_size];((intptr_t)ptr)>=(intptr_t)array;ptr-=array_Head(array)->data_size)array_Maxheapify(array,ptr,compare);
	/*ok, the max heapify had been build, sort it now*/
	last=&((char*)array)[(array_Length(array)-1)*(array_Head(array)->data_size)];
	length=array_Length(array);
	for(ptr=last;ptr>(char*)array;ptr-=(array_Head(array)->data_size))
	{
		memcpy(tmp,array,array_Head(array)->data_size);
		memcpy(array,ptr,array_Head(array)->data_size);
		memcpy(ptr,tmp,array_Head(array)->data_size);
		--array_Length(array);
		array_Maxheapify(array,array,compare);
	};
	array_Length(array)=length;
	return array;
};
